Modern data processing systems typically incorporate address translation schemes. Address translation is a process of mapping the memory address manipulated by the system's data processor into an address presented to the system's memory system. Typically, the address manipulated by the data processing system's data processor is referred to as an "effective" or a "logical" address. Conversely, the address presented to the data processing system's communications bus is referred to as a "real" or a "physical" address.
Address translation schemes improve the performance of a data processing system for at least three reasons. First, address translation schemes may be used to define certain useful characteristics about particular sections of main memory. For instance, these characteristics may prevent the system's data processor from writing to input/output devices during certain modes of operation or may restrict other regions of memory from being cached in the data processor's memory cache. Also, multiple software applications can be resident in the data processor's memory at the same time without fear of one program corrupting another program. Second, address translation schemes allow the data processor to execute programs that are larger than the system's random access memory ("RAM"). The majority of these very large programs are stored in permanent memory devices (hard disk drives, magnetic tape drives, etc.). Smaller portions of these very large programs are recalled into the system's RAM as needed. This feature is known as "virtual memory." Third, more than one data processor in a multi-processor data processing system ("MP") can easily access the same data stored in memory. Each data processor in an MP system can use a different address to access the same location in memory. This feature simplifies software programming of such a system. This feature may also be used by multiple programs executing in a single data processor data processing system.
There are three basic types of address translation schemes: paging, segmentation, and combined paging/segmentation. These three schemes each have advantages and disadvantages with respect to each other known in the art.
In a paging addressing scheme, the main memory is divided into a number of fixed-size blocks ("pages"). A certain number of address bits (most significant bits) of each effective address generated by the data processor identify a selected page in memory. The remaining number of address bits of each effective address (least significant bits) identify a byte within the selected page. Pages are often relatively small. Therefore, page translation data is voluminous and is stored in a table.
In a segmentation addressing scheme, the main memory is divided into a number of variable-size blocks ("segments"). The most and least significant bits of each effective address generated by the data processor identify a segment and a byte within the selected segment, respectively. Originally, a data processing system's operating system program code, its application program code, its application program data, and its pointer stack were each mapped to a different one of four segments in main memory. Consequently, the size of a segment has developed to be several orders of magnitude larger than the size of a page. Segment translation data is smaller and therefore may be stored in either a register file or in a table.
In a paging/segmentation scheme, the main memory is also divided into pages. However, each effective address is mapped to an intermediate or "virtual" address by a segmentation scheme before being mapped to a particular page in main memory. Again, the least significant bits of the effective address are used to identify a byte within the selected page. In some paging/segmentation schemes, both the page and the segments are fixed-size blocks. The PowerPC Architecture uses such an all fixed-size paging/segmentation addressing scheme.
A data processor must translate each effective address into a real address before it can make any memory access. Consequently, the address translation circuitry is often in the data processor's critical "speed path." Unfortunately, known paging/segmentation schemes are becoming only marginally acceptable in light of advances in data processing cycle time. In general, paging/segmentation addressing schemes may be described as serial implementations or as parallel implementations. In a serial implementation, the most significant bits of an effective address ("ESID") are used to index into a segment register file/table to select an virtual segment identifier ("VSID"). The selected VSID is concatenated with the remaining bits of the effective address to form a virtual address. The most significant bits of the virtual address are used to index into a page table to select a real page number ("RPN"). The selected RPN is concatenated with the remaining bits of the virtual address to form the real address. In a parallel implementation, the effective address is used to simultaneously index into a segment register file/table to select a virtual segment identifier ("VSID") and into a page table to select one or more VSID-RRN pairs. The data processor then compares the VSID from the segment table with each VSID from the page table. If one of the comparisons matches, a translation "hit," then the RPN corresponding to the matching VSID is concatenated with the remaining bits of the virtual address to form the real address. Both of these implementations are relatively slow. The first implementation requires two sequential table look-ups. The second implementation requires a single table look-up followed by a comparison.